|
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are some languages that cannot be described by context-free grammars, but can be described by CSG. Context-sensitive grammars are however less general (in the same sense of the term) than unrestricted grammars, i.e. CSG occupy the intermediate position between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSG as non-contracting, although this is not how Noam Chomsky defined it in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the later issue was analyzed by Chomsky in 1963.〔Chomsky, N. 1963. Formal properties of grammar. Handbook of Mathematical Psychology. R.D. Luce, R.R. Bush, & E. Galanter (eds), New York: Wiley. pp. 360-363〕 Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is indeed often the case that a word may or may not be appropriate in a certain place depending upon the context. Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar. Although it is well-known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open research question how much of CSG' expressive power is actually needed to capture the context sensitivity found in natural languages. Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages. ==Formal definition== A formal grammar ''G'' = (''N'', Σ, ''P'', ''S''), where ''N'' is a set of nonterminal symbols, Σ is a set of terminal symbols, ''P'' is a set of production rules, and ''S'' is the start symbol, is context-sensitive if all rules in ''P'' are of the form : α''A''β → αγβ where ''A'' ∈ ''N'',〔i.e., ''A'' is a single nonterminal〕 α,β ∈ (''N''∪Σ) * 〔i.e., α and β are strings of nonterminals and terminals〕 and γ ∈ (''N''∪Σ)+.〔i.e., γ is a nonempty string of nonterminals and terminals〕 A string ''u'' ∈ (''N''∪Σ) * directly yields, or directly derives to, a string ''v'' ∈ (''N''∪Σ) *, denoted as ''u'' ⇒ ''v'', if ''u'' can be written as ''l''α''A''β''r'', and ''v'' can be written as ''l''αγβ''r'', for some production rule (α''A''β→αγβ) ∈ ''P'', and some context strings ''l'', ''r'' ∈ (''N''∪Σ) *. More generally, ''u'' is said to yield, or derive to, ''v'', denoted as ''u'' ⇒ * ''v'', if ''u'' = ''u''1 ⇒ ... ⇒ ''u''''n'' = ''v'' for some ''n''≥0 and some strings ''u''2, ..., ''u''''n''-1 (''N''∪Σ) *. That is, the relation (⇒ *) is the reflexive transitive closure of the relation (⇒). The language of the grammar ''G'' is the set of all terminal symbol strings derivable from its start symbol, formally: ''L''(''G'') = . Derivations that do not end in a string composed of terminal symbols only are possible, but don't contribute to ''L''(''G''). The only difference between this definition of Chomsky and that of unrestricted grammars is that γ can be empty in the unrestricted case.〔 Some definitions of a context-sensitive grammar only require that for any production rule of the form u → v, the length of u shall be less than or equal to the length of v. This seemingly weaker requirement is in fact weakly equivalent,〔; p.223-224; Exercise 9, p.230. In the 2003 edition, the chapter on CSG has been omitted.〕 see Noncontracting grammar#Transforming into context-sensitive grammar. In addition, a rule of the form : ''S'' → λ where λ represents the empty string and ''S'' does not appear on the right-hand side of any rule is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the context free languages, rather than having to make the weaker statement that all context free grammars with no →λ productions are also context sensitive grammars. The name ''context-sensitive'' is explained by the α and β that form the context of ''A'' and determine whether ''A'' can be replaced with γ or not. This is different from a context-free grammar where the context of a nonterminal is not taken into consideration. Indeed, every production of a context free grammar is of the form ''V'' → ''w'' where ''V'' is a ''single'' nonterminal symbol, and ''w'' is a string of terminals and/or nonterminals; ''w'' can be empty. If the possibility of adding the empty string to a language is added to the strings recognized by the noncontracting grammars (which can never include the empty string) then the languages in these two definitions are identical. The left-context- and right-context-sensitive grammars are defined by restricting the rules to just the form α''A'' → αγ and to just ''A''β → γβ, respectively. The languages generated by these grammars are also the full class of context-sensitive languages.〔 also at http://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive〕 The equivalence was established by Penttonen normal form.〔 citing 〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Context-sensitive grammar」の詳細全文を読む スポンサード リンク
|